//1.脑瘫做法
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<pair<int,int>> temp;



        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n;++j) {
                if(matrix[i][j] == 0) 
                   temp.push_back({i,j});
            }
        }
        int k=0;
        while(k < temp.size()) {
           
            matrix[temp[k].first].assign(matrix[0].size(), 0); 
            for(int i = 0; i < m; ++i) {                     
                matrix[i][temp[k].second]=0;
            }   
            k++;  
        }
        
        return;
    }
};


///2.时间-> O(mn)，空间->O(m+n)
//使用两个标记数组分别记录需要置零的行和列，避免重复置零操作。
class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        vector<int> row(m,0);
        vector<int> col(n,0);
        for(int i=0;i<m;++i){
            for(int j =0;j<n;++j){
                if(matrix[i][j]==0) {
                    row[i]=1;   //标记行
                    col[j]=1;   //标记列
                }

            }
        }
        for(int i=0;i<m;++i){
            for(int j =0;j<n;++j){
                if(row[i] || col[j])
                    matrix[i][j]=0;
                

            }
        }
        
        return;
    }
};

///3.空间复杂度：O(1)


class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        int flag_col0 = false, flag_row0 = false;
        for (int i = 0; i < m; i++) {
            if (!matrix[i][0]) {
                flag_col0 = true;
            }
        }
        for (int j = 0; j < n; j++) {
            if (!matrix[0][j]) {
                flag_row0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][j]) {
                    matrix[i][0] = matrix[0][j] = 0;
                }
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (!matrix[i][0] || !matrix[0][j]) {
                    matrix[i][j] = 0;
                }
            }
        }
        if (flag_col0) {
            for (int i = 0; i < m; i++) {
                matrix[i][0] = 0;
            }
        }
        if (flag_row0) {
            for (int j = 0; j < n; j++) {
                matrix[0][j] = 0;
            }
        }
    }
};





